#include <stdlib.h>
#include "sort.h"
#include "func.h"

int pick(int *a, int head, int tail)
{
	int i = head;
	int j = tail;
	int key = a[head];

	while(i != j)
	{
		if(a[j] < key)
		{
			a[i] = a[j];
			while(1)
			{
				i++;
				if(i == j)
					break;

				if(a[i] > key)
				{
					a[j] = a[i];
					j--;
					break;
				}
			}
		}
		else
			j--;
	}
	a[j] = key;

	return i;
}
void quicksort(int *a, int head, int tail)
{
	int pos = 0;

	if(head < tail)
	{
		pos = pick(a, head, tail);
		quicksort(a, head, pos);
		quicksort(a, pos+1 , tail);
	}
}
void sort_quick(int *a, int n)
{
	quicksort(a, 0, n-1);
}